446. Arithmetic Slices II - Subsequence

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

• 先卡位，今天打疫苗，開始發燒了
• 9/11補上

題目解釋

你會得到一組陣列，請從陣列中找出所有可以組成的等差數列，但是有以下條件:

1. 等差數列的要包含至少3個數字
2. 必須按照陣列數字原有的順序找出等差數列

example

解法

這題我覺得很難，看著別人的答案只覺得，能想到這個解法的不是人吧!

所以我盡量用淺顯易懂的方式說明別人的解法

先看看程式碼吧

程式碼

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        
        dp = [defaultdict(int) for i in range(len(nums))]
        ans = 0
        
        for i in range(len(nums)):
            for j in range(i):
                difference = nums[i] - nums[j]
                dp[i][difference] += dp[j][difference] + 1
                ans += dp[j][difference]
        return ans
                

這題要用動態規劃(dp)來解，而dp要記錄的東西請看下圖

表格的y 方向是陣列的所有數字，表格的x 方向紀錄數字之間會出現的差

而表格內的數字則代表到目前為止，有包含該數字的等差數列有幾個

例如:

上圖中:
(陣列4，差2)的數字就代表數字4在目前組出等差為2的數列出現1次 --> [2,4]
(陣列6，差2)的數字就代表數字6在目前組出等差為2的數列出現2次 --> [2,4,6]、[4,6]
(陣列8，差2)的數字就代表數字8在目前組出等差為2的數列出現3次 --> [2,4,6,8]、[4,6,8]、[6,8]

這些步驟就是這段程式在做的

difference = nums[i] - nums[j]
dp[i][difference] += dp[j][difference] + 1

而我們要回傳有幾組符合條件的，則靠這行程式去紀錄:

ans += dp[j][difference]

這行的意思我們再借用上圖來解釋:

(陣列6，差2)的數字就代表數字6在目前組出等差為2的數列出現2次 --> [2,4,6]、[4,6]
(陣列8，差2)的數字就代表數字8在目前組出等差為2的數列出現3次 --> [2,4,6,8]、[4,6,8]、[6,8]

當我們再計算(陣列8，差2)的數字是多少時，這裡ans 會記錄(陣列6，差2)裡的2

這代表數字8讓*[2,4,6]、[4,6]* 變成*[2,4,6,8]、[4,6,8]*，所以我們紀錄(陣列6，差2)裡的2

閒聊

還在發燒中